1. Technical Field
The invention is related to error correction encoders useful with interleaved data encoded with an outer cyclic error correction code of the type employed, for example, in the compact audio disk industry standard, in which a parallel encoder is typically required because the format is such that the parity characters are in the middle of the codeword.
2. Background Art
In data recording systems, such as the industry standard compact audio disk system, it is necessary to be able to correct not only short random errors in the data but also long bursts of errors occurring therein. A well-known technique is to interleave the data, encode it with an outer error correction code, interleave the outer error correction encoded data, encode the interleaved outer error correction encoded data with an inner error correction code and finally interleave the inner error correction encoded data. Each of the three interleaving steps can perform a different interleaving scheme, as desired. As one example of such a system, the industry standard compact audio disk system employs an outer error correction code in which the check portion, containing the parity characters, is in the middle of the codeword, having message characters on either side of it. The outer code employed is a (28,24) shortened Reed-Solomon code over GF(2.sup.8) in which the first twelve characters in the outer codeword are message characters, the middle four characters are parity characters and the last twelve characters are message characters. The inner code in the compact audio disk standard does not have the check portion in the middle of the inner codeword but rather at the end of the codeword.
The advantage of this system is that, while the encoding process in the recording system is relatively time-consuming, both burst errors and random errors are simply and quickly corrected in the decoder during retrieval or playback of the data, as described in U.S. Pat. No. 4,413,340 to Odaka et al. and assigned to Sony Corporation. This feature minimizes the cost of a compact audio disk player. The referenced Odaka et al. patent describes the inner and outer error correction encoders as well as the interleaving schemes employed at the input and output of each encoder in the industry standard compact audio disk system.
Typically, such systems are intended for use where the speed of recording need not be particularly fast. Such is the case, for example, in the industry standard compact audio disk system in which digital stereo sound is permanently recorded on a master optical disk by a laser beam. The optical pattern thus produced on the master disk is then easily and quickly reproduced on a large number of disks which are then made available to the public. The only requirement is that the decoder in the compact audio disk player keep up with the playback of the data. It does not matter how long the encoder takes to process the data for recording on the master disk. Accordingly, the encoding system described in the above-referenced Odaka et al. patent is not particularly fast. In fact, the speed of the encoder is limited by the nature of the outer code chosen for the industry standard compact audio disk system.
The recording system of the compact audio disk system as described in the above-referenced Odaka et al. patent employs parallel interleavers and parallel encoders which require the simultaneous presence of all characters to be interleaved at each interleaver and to be encoded at each encoder. Thus, the first interleaver must completely interleave all incoming message characters in an incoming data block before the outer encoder can begin encoding to form an outer codeword, and the second interleaver must finish interleaving the outer codeword before the inner encoder can begin encoding the interleaved outer codeword. Thus, there are inherent delays which are unavoidable in a system employing parallel encoders and parallel interleavers. Such delays would not be present in a serial system which serially interleaves and serially encodes the message characters as they are received one character at a time. Such a serial system cannot function using the parallel encoders described above and must instead use serial encoders in place thereof. Unfortunately, the outer parallel Reed Solomon encoder used in the compact audio disk system cannot be replaced by a serial Reed Solomon encoder, because the serial Reed Solomon encoder will not provide the correct parity characters for the outer codeword.
Specifically, since the outer code requires that the check characters of the outer codeword be located in the middle of the word (i.e., in "intermediate" symbol locations in the codeword), it is not possible to encode the data in serial fashion using a conventional byte serial encoder in accordance with the outer code. This is because the value of the parity characters depends in part upon their location within the codeword, and conventional byte-serial encoders can only compute parity characters for placement at the end of the codeword. The degree of the polynomial corresponding to the check characters generated by a serial encoder is lower than the degree of the polynomial representing the message characters, and therefore the check characters generated by a serial encoder correspond to symbol locations at the end of the codeword only. As described, for example, in Peterson, W. W., and E. J. Weldon, Jr., Error-Correcting Codes, Ed. II, MIT Press (1972), all of the message characters are shifted through a serial encoder, and when this is done the serial encoder contains the parity characters which are to be appended at the end of all the message characters to form a codeword.
One way around the apparent inability of a serial encoder to compute parity characters having intermediate symbol locations would be to cyclically shift to the left-most symbol locations all of the message characters located in symbol locations to the right of the parity characters, so that the parity characters would be located at the end of the shifted codeword. However, the code is a shortened cyclic code, as mentioned above. Therefore, the resulting shifted codeword would consist, from left to right, of a group of message characters in the left-most symbol locations, a long string of zero-valued characters in intermediate symbol locations and the remaining message characters immediately followed by the parity characters in the right-most symbol locations. The length of the string of zero-valued characters is equal to the size of the code minus the number of message and parity characters in the shortened codeword. Since parity characters in the shifted codeword are located at the end of the codeword, a conventional byte-serial shift register encoder can be used to compute them. Unfortunately, this would not necessarily speed up the encoding process as might be expected because of the extra time wasted as the string of zero-valued characters in the middle of the new codeword is shifted through the serial encoder. (For the reader not familiar with algebraic coding theory, it should be noted that the serial encoder in this case must actually shift all of the zero-valued characters through itself in order to arrive at the right answer, and not simply "skip ahead" past the string of zero-valued characters to the next group of message characters to avoid wasting time.) In the case of the industry standard compact audio disk system, the size of the code is 255 and there are 24 message characters and 4 parity characters, so that the length of the string of zeros in the shifted codeword would be 227. In order to compute the parity characters, the 24 message characters and the 227 zero-valued characters would have to be shifted through the serial encoder, for a total of 251 shifts. The extra 227 shifts (and computations) which must be performed by the serial encoder in such a case would represent an unacceptable delay and is therefore not feasible.
Thus, given the choice of the outer error correction code as a shortened cyclic code having check characters located in intermediate symbol locations, a serial encoder cannot be employed in systems such as the industry standard compact audio disk system. Accordingly, the delays described above which are inherent in a parallel interleaving and encoding system such as the industry standard compact audio disk system appear to be unavoidable. Therefore, it has seemed that there is no practical way to increase the speed at which data can be recorded in a system employing a code in which the parity characters are in intermediate symbol locations.